The invention relates to digital data processing and, more particularly, to methods and apparatus for executing programs on parallel processing computers.
Early computers typically relied on a single processing unit, or CPU, to perform processing functions. Source code programs written for those computers were translated into a sequence of machine instructions which were then executed one-by-one by the CPU. Where repetitive sequences of steps, or loops, existed in the original program, the single processor would take up each instruction in the loop, one at a time, and repeat those same instructions for each iteration of the loop.
A later advance made it possible to execute some sets of instructions "in parallel" with one another. This advance, referred to as co-processing, provided alongside the CPU a special purpose processor. Execution of programs on such a machine was thus divided between the coprocessor and the CPU.
With the advent of computers with multiple processors, it became possible to allocate entire tasks to separate concurrently operating CPU's. A special class of these multiprocessors, referred to as parallel processors, are equipped with special synchronizing mechanisms and thus are particularly suited for concurrently executing portions of the same program.
"Parallelizing" execution of computer programs so that they can be run efficiently on parallel processors is a daunting task. First, the data-flow and control-flow of the program must be understood and, then, rearranged to define a set clearly divisible tasks. The most significant gains attained to date have been in the rearrangement of loop execution, i.e., "loop interchange," synchronization and (to a limited degree) tiling.
Although much parallelization work is done by hand, recent inroads have been made into automating that task. This is typically performed in connection with the compilation process, which converts the source code program into machine code. One commercially available product, the KAP/KAI Preprocessor available from Kuck and Associates, Inc., of Illinois, performs some of these functions. Particularly, that preprocessor provides capabilities for loop interchange and synchronization.
In view of the foregoing, an object of this invention is to provide improved digital data processing apparatus and methods.
More particularly, an object is to provide an improved mechanism for executing programs on parallel processing computers, including those which are massively parallel.
Still another object is to provide an improved compiler for facilitating parallelization of computer programs.
Yet another object is to provide a computer run-time mechanism for parallelizing and executing a computer program on a multiprocessor system.